#include <iostream>
#include <vector>
using namespace std;
class MinSqueue
{
public:
    vector<int> heap;
    int size;
    MinSqueue(int size, int a[]);
    void minHeap(int i, int size); //keep the feature of minheap
    void swap(int &a, int &b);
    void heapSort(int size);
    int heap_min()
    {
        return heap[0];
    }
    int heap_extract_min(int n);
};
MinSqueue::MinSqueue(int size, int a[])
{
    for (int i = 0; i < size; ++i)
        heap.push_back(a[i]);
    for (int i = size / 2; i > 0; --i)
    {
        minHeap(i, size);
    }
    this->size = size;
}
void MinSqueue::minHeap(int i, int size)
{
    int smallest, left, right;
    left = 2 * i;
    right = 2 * i + 1;
    if (heap[left - 1] < heap[i - 1] && left <= size)
        smallest = left;
    else
        smallest = i;
    if (heap[right - 1] < heap[smallest - 1] && right <= size)
        smallest = right;
    if (smallest != i)
    {
        swap(heap[smallest - 1], heap[i - 1]);
        minHeap(smallest, size);
    }
}
void MinSqueue::swap(int &a, int &b)
{
    int c = a;
    a = b;
    b = c;
}
void MinSqueue::heapSort(int size)
{
    int i = size;
    for (; i > 0; --i)
    {
        swap(heap[i - 1], heap[0]);
        --size;
        minHeap(1, size);
    }
}
int MinSqueue::heap_extract_min(int n)
{
    if (n < 1)
        return 0;
    int min = heap[0];
    heap[0] = heap[n - 1];
    n--;
    minHeap(1, n);
    return min;
}
int main()
{
    int a[]={ 4,1,3,2,16,9,10,14,8,7 };
    int i;
    MinSqueue squeue(10,a);
    for (i = 0; i < 10;++i)
        cout << squeue.heap[i] << " ";
    
    cout << squeue.heap_extract_min(squeue.size);
    cout << endl;
    for (i = 0; i < 10;++i)
        cout << squeue.heap[i] << " ";
}